package com.cdream.basic.algorithm.leetcode.array;

import java.util.ArrayList;
import java.util.List;

/**
 * @author cdream
 * @date 10/22/21
 */
public class Question229 {
    public static void main(String[] args) {
        new Question229().majorityElement(new int[]{1, 1, 1, 3, 3, 2, 2, 2});
    }

    public List<Integer> majorityElement(int[] nums) {
        int num1 = 0;
        int num2 = 0;
        int count1 = 0;
        int count2 = 0;
        // 是num1 / num2 与其他三方数的战斗，num1,num2不会互相伤害，大于1／3的数最终会在抵消战斗中存活下来
        for (int num : nums) {
            if (count1 > 0 && num1 == num) {
                count1++;
            } else if (num2 == num && count2 > 0) {
                count2++;
            } else if (count1 == 0) {
                num1 = num;
                count1++;
            } else if (count2 == 0) {
                num2 = num;
                count2++;
            } else {
                count1--;
                count2--;
            }
        }
        count1 = 0;
        count2 = 0;
        // 存活下来的两个数未必是结果，需要进一步验证
        for (int num : nums) {
            if (num == num1) {
                count1++;
            }
            if (num == num2) {
                count2++;
            }
        }
        List<Integer> res = new ArrayList<>();
        // 校验
        if (count2 * 3 > nums.length) {
            res.add(num2);
        }
        if (count1 * 3 > nums.length) {
            res.add(num1);
        }
        return res;
    }

    public String[] findOcurrences(String text, String first, String second) {
        List<String> list = new ArrayList<String>();
        String[] t = text.split(" ");
        for (int i = 0; i < t.length - 2; i++) {
            if (first.equals(t[i]) && second.equals(t[i + 1])) {
                list.add(t[i + 2]);
            }
        }
        return list.toArray(new String[]{});
    }
}
